package book;

public class SubArraySolution {
    // 求子数组 a[left..right] 的最大子数组和
    int maxSum(int[] a, int left, int right) {
        if (left == right) return a[left]; // 仅一个元素时直接返回

        // 第1步：划分
        int mid = left + (right - left) / 2;
        
        // 第2步：求解子问题
        int s1 = maxSum(a, left, mid);      // 递归求左子数组
        int s2 = maxSum(a, mid + 1, right); // 递归求右子数组

        // 求中间段的和
        int maxleft = 0, maxright = 0, ls = 0, rs = 0;
        for (int i = mid; i >= left; i--) 
            maxleft = Math.max(maxleft, ls += a[i]);
        for (int j = mid + 1; j <= right; j++) 
            maxright = Math.max(maxright, rs += a[j]);
 
        // 第3步：合并解并返回
        int max_s = Math.max(s1, s2);
        if (maxleft + maxright > 0) 
            max_s = Math.max(max_s, maxleft + maxright);

        return max_s;
    }

    public static void main(String[] args) {
        int[] a = { -20, 10, -30, 40, -10, 20, 10, -50, 40 };
        int sum = new SubArraySolution().maxSum(a, 0, a.length - 1);
        System.out.println("最大子数组和为：" + sum);
    }
}
